#region MIT Licence
/*
 * Copyright (C) 2014 PdfCreative
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
 * and associated documentation files (the "Software"), to deal in the Software without restriction, 
 * including without limitation the rights to use, copy, modify, merge, publish, distribute, 
 * sublicense, and/or sell copies of the Software, and to permit persons to whom 
 * the Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included 
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
 * AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.IO.Compression;
using System.Text;

using PdfCreative.Pdf.Writer;
using PdfCreative.Pdf.Writer.Embedding.Predictors;
using PdfCreative.Pdf.Writer.Utilities;

namespace PdfCreative.Pdf.Writer.Embedding
{
    /// <summary>
    /// The PdfParser class parses objects from a PDF document. It uses a PdfLexer to read PDF tokens and combine them
    /// into objects. The PdfParser also provides access to object values including indirect object references.
    /// </summary>
    internal class PdfParser
    {
        // Private fields
        // ==============
        #region Private fields
        private Dictionary<PdfObjectReference, CrossReference> _crossReferenceLookup;
        private List<CrossReference> _crossReferences;
        private PdfObjectReference _documentRoot;
        private Stream _in;
        private PdfLexer _lexer;
        private byte[] _endStream = System.Text.ASCIIEncoding.ASCII.GetBytes("endstream");
        private List<PdfObjectReference> _objectStreams;
        #endregion

        #region Parser state
        private int _bytesLeft;
        private PdfObject _currentObject;
        private PdfParseState _state;
        private ParserStreamType _streamType;
        #endregion



        // Public events
        // =============
        #region Public events
        /// <summary>
        /// The BeginObject event is raised when the parser has found the start of an object.
        /// </summary>
        public event PdfObjectReferenceEventHandler BeginObject;

        /// <summary>
        /// The EndObject event is raised when the parser has finished reading an object.
        /// </summary>
        public event PdfObjectReferenceEventHandler EndObject;

        /// <summary>
        /// The Object event is raised when an object's contents has been fully read. This event
        /// is fired before the Stream event.
        /// </summary>
        public event PdfObjectEventHandler Object;

        /// <summary>
        /// The Stream event is raised when an object stream has been encountered. Not all objects
        /// have streams, so this event is not raised for every object. It is raised after the
        /// Object event, before the EndObject event.
        /// </summary>
        public event PdfObjectReferenceEventHandler Stream;
        #endregion



        // Public properties
        // =================
        #region Public properties
        /// <summary>
        /// Retrieves the list of cross-references in the document.
        /// </summary>
        public List<CrossReference> CrossReferences
        {
            get { return _crossReferences; }
        }

        /// <summary>
        /// Retrieves the root object of the document.
        /// </summary>
        public PdfObjectReference DocumentRoot
        {
            get { return _documentRoot; }
        }
        #endregion



        // Public methods
        // ==============
        #region Public methods
        /// <summary>
        /// Parses all the objects in the document.
        /// </summary>
        public void ParseAllObjects()
        {
            // We are now in the Free state.
            _state = PdfParseState.Free;

            // We go through the cross-references in the document, and parse the referenced objects.
            // We will only read cross-references based on an offset in the file - if objects are
            // Object Streams then we will read the contained objects at the appropriate moment.
            foreach (CrossReference crossReference in _crossReferences)
            {
                // Exit as soon as we find an Object Stream reference.
                if (CrossReferenceType.ObjectStream == crossReference.Type)
                    break;

                SeekAndParse(crossReference, true);                
            }
        }

        /// <summary>
        /// Parses the document's header. This parses the document's cross-reference tables and its root.
        /// </summary>
        /// <returns>A boolean value that indicates if the operation was completed successfully.</returns>
        public bool ParseDocumentHeader()
        {
            // The first thing we need to do is read the source document's cross-reference table.
            long startXRef = FindStartXRef();

            // Then we read all the cross-reference tables, and store the cross-references. These will allow
            // the PdfParser to locate objects within the PDF document.
            ReadCrossReferenceTables(startXRef);

            // We sort the cross-references on location.
            SortCrossReferences();

            return true;
        }

        /// <summary>
        /// Parses the specified object.
        /// </summary>
        /// <param name="obj">The object</param>
        public void ParseObject(PdfObjectReference obj)
        {
            // We are now in the Free state.
            _state = PdfParseState.Free;

            if (null == obj) throw new ArgumentNullException("obj");
            if (obj.IsEmpty()) throw new ArgumentException("PDF Object reference cannot be empty", "obj");

            CrossReference crossReference = _crossReferences.Find(match => match.Equals(obj));

            if (null != crossReference)
                SeekAndParse(crossReference, false);
            else
                throw new PdfParserException("No cross-reference was found that matches object {0}", obj);
        }

        /// <summary>
        /// Reads a part of a currently open stream within an object. This operation only works when
        /// a stream has been openened; a method call to ReadStreamChunk should follow the receipt of a
        /// Stream event raised by this PdfParser instance.
        /// </summary>
        /// <param name="buffer">A buffer to read bytes in</param>
        /// <param name="startIndex">The start index in the buffer to start copying into</param>
        /// <param name="length">The length of bytes to read</param>
        /// <returns>The number of bytes copied into the buffer.</returns>
        public int ReadStreamChunk(byte[] buffer, int startIndex, int length)
        {
            if (null == buffer) throw new ArgumentNullException("buffer");
            if (startIndex < 0) throw new ArgumentOutOfRangeException("startIndex");
            if (length < 0) throw new ArgumentOutOfRangeException("length");
            if (_state < PdfParseState.BeginStream)
                throw new InvalidOperationException(
                    "The ReadStreamChunk method can only be invoked when the parser has encountered a stream.");

            System.Diagnostics.Debug.Assert(null != _currentObject);

            int bytesRead = 0;

            // If the stream does not have an encoding then we consider it to be a PDF token stream.
            // Otherwise, we consider its data to be in binary form.
            // A PDF token stream with a known length can also be read as a binary stream. It is illegal
            // for an encoded stream to have no length.
            if (PdfParseState.BeginStream == _state)
            {
                _bytesLeft = ReadIndirectInt32(_currentObject.Dictionary.GetValue("/Length"));
                string streamFilter = ReadIndirectString(_currentObject.Dictionary.GetValue("/Filter"));

                if(false==String.IsNullOrEmpty(streamFilter))
                {
                    if (_bytesLeft > 0)
                        _streamType = ParserStreamType.Binary;
                    else
                        throw new PdfParserException(
                            "The stream in object {0} uses a filter, but does not have a length set.",
                            _currentObject.Identifier);
                }
                else
                {
                    if(_bytesLeft > 0)
                        _streamType = ParserStreamType.Binary;
                    else
                        _streamType = ParserStreamType.PdfToken;
                }
            }

            // Depending on the type of the stream we delegate to either of two methods.
            switch (_streamType)
            {
                case ParserStreamType.Binary:
                    bytesRead = ReadBinaryStreamChunk(buffer, startIndex, length);
                    break;

                case ParserStreamType.PdfToken:
                    bytesRead = ReadPdfTokenStreamChunk(buffer, startIndex, length);
                    break;
            }

            return bytesRead;
        } // ReadStreamChunk()

        /// <summary>
        /// Reads a dictionary that may be an indirect object value.
        /// If the supplied value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <returns>The actual value or the indirect value.</returns>
        public PdfDictionary ReadIndirectDictionary(PdfValue value)
        {
            return ReadIndirectValue(value) as PdfDictionary;

        } // ReadIndirectInt32()


        /// <summary>
        /// Reads an integer value that may be an indirect object value.
        /// If the supplied value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <returns>The actual value, or 0 if the original value is not a valid integer.</returns>
        public int ReadIndirectInt32(PdfValue value)
        {
            return ReadIndirectInt32(value, default(int));
        } // ReadIndirectInt32()

        /// <summary>
        /// Reads an integer value that may be an indirect object value.
        /// If the supplied value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <param name="defaultValue">The default value to use if the original value
        /// is not a valid integer</param>
        /// <returns>The actual value, or the default if the original value is not a valid integer.</returns>
        public int ReadIndirectInt32(PdfValue value, int defaultValue)
        {
            int result = defaultValue;

            PdfValue indirectValue = ReadIndirectValue(value);
            if (null != indirectValue)
                if (false == Int32.TryParse(indirectValue.ToString(), out result))
                    result = defaultValue;

            return result;
        } // ReadIndirectInt32()

        /// <summary>
        /// Reads an long integer value that may be an indirect object value.
        /// If the supplied value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <returns>The actual value, or 0 if the original value is not a valid long integer.</returns>
        public long ReadIndirectLong(PdfValue value)
        {
            return ReadIndirectLong(value, 0L);
        } // ReadIndirectLong()

        /// <summary>
        /// Reads a long integer value that may be an indirect object value.
        /// If the supplied value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <param name="defaultValue">The default value to use if the original value
        /// is not a valid integer</param>
        /// <returns>The actual value, or the default if the original value is not a valid long integer.</returns>
        public long ReadIndirectLong(PdfValue value, long defaultValue)
        {
            long result = defaultValue;

            PdfValue indirectValue = ReadIndirectValue(value);
            if (null != indirectValue)
                if (false == Int64.TryParse(indirectValue.ToString(), out result))
                    result = defaultValue;

            return result;
        } // ReadIndirectLong()

        /// <summary>
        /// Reads a string value that may be an indirect object value.
        /// If the supplied value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <returns>The actual value or a Null reference.</returns>
        public string ReadIndirectString(PdfValue value)
        {
            string result = null;

            PdfValue indirectValue = ReadIndirectValue(value);
            if (null != indirectValue)
                result = indirectValue.ToString();

            return result;
        } // ReadIndirectInt32()

        /// <summary>
        /// Reads a value that may be an indirect object value.
        /// If the value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <returns>The actual value</returns>
        public PdfValue ReadIndirectValue(PdfValue value)
        {
            return ReadIndirectValue(value, SeekLocation.FileAndObjectStream);
        }

        /// <summary>
        /// Reads a value that may be an indirect object value.
        /// If the value is an object reference, it will be parsed and its value returned.
        /// If not, the original value is returned.
        /// </summary>
        /// <param name="value">The original value</param>
        /// <param name="seekLocation">The locations to look for the value;
        /// FileOnly to look in objects that are not stored in object streams.
        /// FileAndObjectStream to look in regular objects as well as objects in object streams.</param>
        /// <returns>The actual value</returns>
        public PdfValue ReadIndirectValue(PdfValue value, SeekLocation seekLocation)
        {
            PdfValue result = null;

            if (value is PdfObjectReference)
            {
                // Remember the lexer's current position.
                _lexer.PreserveState();

                // We try to locate the object in the source stream.
                bool foundValue = false;
                PdfObjectReference reference = value as PdfObjectReference;
                CrossReference crossReference = _crossReferences.Find(match => match.Equals(reference));
                if (null != crossReference)
                {
                    // If the object is located inside an object stream but the seek location indicates that
                    // we can't, then we throw an exception.
                    // If the object is located inside the current object, we cancel the search -
                    // an object stream's dictionary cannot refer to objects defined in itself!
                    if (CrossReferenceType.ObjectStream == crossReference.Type)
                    {
                        if (SeekLocation.FileOnly == seekLocation)
                            throw new PdfParserException("Object {0} is not allowed to be inside an object stream.", reference);

                        if (_currentObject.Identifier.Equals(crossReference.ParentReference))

                            throw new PdfParserException(
                                "The object stream {0} references an object {1} that is a child of itself",
                                _currentObject.Identifier,
                                reference);
                    }

                    PdfLexer lexer = SeekObject(crossReference);
                    if (null != lexer)
                    {
                        // If we found it, we can read its values.
                        PdfObject theObject = new PdfObject();
                        theObject.Parse(lexer);

                        // We have found the indirect value.
                        result = theObject.Value;
                        foundValue = true;

                        // And finally, restore the parser's lexer to its previous state.
                        _lexer.RestoreState();
                    }
                }

                if(false==foundValue)
                    throw new PdfParserException("Object '{0}' could not be found in the document.", value);

            }
            else
                result = value;

            return result;
        } // ReadIndirectValue()
        #endregion



        // Private implementation
        // ======================
        #region Event stubs
        /// <summary>
        /// Raises the BeginObject event.
        /// </summary>
        /// <param name="obj">The object reference.</param>
        protected void OnBeginObject(PdfObjectReference obj)
        {
            if (null != BeginObject)
                BeginObject(obj);
        }

        /// <summary>
        /// Raises the EndObject event.
        /// </summary>
        /// <param name="obj">The object reference.</param>
        protected void OnEndObject(PdfObjectReference obj)
        {
            if (null != EndObject)
                EndObject(obj);
        }

        /// <summary>
        /// Raises the Object event.
        /// </summary>
        /// <param name="obj">The object.</param>
        protected void OnObject(PdfObject obj)
        {
            if (null != Object)
                Object(obj);
        }

        /// <summary>
        /// Raises the Stream event.
        /// </summary>
        /// <param name="obj">The object that the stream belongs to.</param>
        protected void OnStream(PdfObjectReference obj)
        {
            if (null != Stream)
                Stream(obj);
        }
        #endregion

        #region Parsing objects
        /// <summary>
        /// Parses the object stream at the current position in the specified lexer. 
        /// This method will parse the objects contained within the stream.
        /// </summary>
        /// <param name="containingLexer">The containing object's lexer</param>
        private void ParseObjectStream(PdfLexer containingLexer)
        {
            containingLexer.Read(); // read whitespace

            // We create a new Lexer based on the object's stream. This means we are
            // looking for a decoder that will handle the encoding, and create a decoding
            // stream that plugs into the underlying lexer's stream.
            int length = PdfValue.ReadInt32(
                ReadIndirectValue(_currentObject.Dictionary.GetValue("/Length"), SeekLocation.FileOnly));
            int numberOfObjects = ReadIndirectInt32(_currentObject.Dictionary.GetValue("/N"));
            long offset = ReadIndirectLong(_currentObject.Dictionary.GetValue("/First"));
            string filter = ReadIndirectString(_currentObject.Dictionary.GetValue("/Filter"));
            DecoderStream decoder = DecoderStream.GetDecoder(filter);
            if (null != decoder)
            {
                decoder.Initialise(
                    containingLexer.OpenStream(length),
                    ReadIndirectDictionary(_currentObject.Dictionary.GetValue("/DecodeParms")));

                PdfLexer lexer = new PdfLexer(decoder);

                // Read the offsets of the objects.
                List<CrossReference> objectOffsets = new List<CrossReference>();
                for (int objectEnum = 0; objectEnum < numberOfObjects; objectEnum++)
                    objectOffsets.Add(new CrossReference(
                        new PdfObjectReference(ConversionUtilities.ReadInt32(lexer.ReadNextToken())),
                        ConversionUtilities.ReadLong(lexer.ReadNextToken())));

                // Go through the list of objects to be embedded.
                // We make sure each object is listed in the document's cross-references tables.
                long lastLocation = -1L;
                foreach (CrossReference sourceReference in objectOffsets)
                {
                    if (IsListed(sourceReference.ObjectReference) &&
                        sourceReference.Location > lastLocation)
                    {
                        // Move forward to the actual location of the object.
                        lexer.ReadAhead(sourceReference.Location + offset);

                        // Parse the object. Streams are illegal in objects within an object stream.
                        PdfObject containedObject = new PdfObject();
                        containedObject.Identifier = sourceReference.ObjectReference;
                        containedObject.Stream += delegate()
                        {
                            throw new PdfParserException(
                                "Illegal stream encountered in object {0}, within object stream of object {1}",
                                containedObject.Identifier,
                                _currentObject.Identifier);
                        };

                        // Start parsing the object.
                        OnBeginObject(sourceReference.ObjectReference);
                        containedObject.Parse(lexer, true);

                        // Inform listeners of the new object. We are done with this object.
                        OnObject(containedObject);
                        OnEndObject(sourceReference.ObjectReference);

                        // Remember where this object was in the object stream.
                        lastLocation = sourceReference.Location;

                    } // If the object has a known ID
                    else
                    {
                        // This is an object inside the object stream that is not listed in the
                        // document's cross-reference tables. We won't parse it.
                        throw new PdfParserException(
                            "Unknown object in object stream of object {0}", _currentObject.Identifier);
                    }

                } // for each object

            } // If we have found a decoder
            else
                throw new PdfParserException(
                    "No decoder found to match filter '{0}' in object stream of object {1}",
                    filter, _currentObject.Identifier);
        }

        /// <summary>
        /// Seeks the object indicated by the specified cross-reference, and parses it.
        /// </summary>
        /// <param name="crossReference">The cross-reference</param>
        /// <param name="parseContainedObjects">True if this method will parse objects within an
        /// object stream, False if the contents of an object stream are to be ignored.</param>
        private void SeekAndParse(CrossReference crossReference, bool parseContainedObjects)
        {
            // Look for the object. We will use the provided lexer.
            PdfLexer lexer = SeekObject(crossReference);

            if (null != lexer)
            {
                // We notify listeners of the newly located object. We are now in the
                // 'Object' state.
                _state = PdfParseState.Object;
                OnBeginObject(crossReference.ObjectReference);

                // We set up a PDF object to parse. It's possible that the object contains a stream,
                // which we will have to handle here.
                bool hasNotified = false;
                _currentObject = new PdfObject();
                _currentObject.Identifier = crossReference.ObjectReference;
                _currentObject.Stream += delegate()
                {
                    // Notify the listeners of the object contents.
                    OnObject(_currentObject);

                    // We have found a stream. If this object is an Object Stream and we are parsing
                    // contained objects then we handle the stream. Otherwise, we raise the Stream event.
                    // objects
                    if ("/ObjStm" == _currentObject.Type && true == parseContainedObjects)
                    {
                        // This ends the containing object.
                        OnEndObject(crossReference.ObjectReference);

                        // Not all object stream objects are necessarily used - we make sure that
                        // this one is, and then parse the object stream.
                        if(_objectStreams.Contains(crossReference.ObjectReference))
                            ParseObjectStream(lexer);
                    }
                    else
                    {
                        // Raise the Stream event and end this object.
                        _state = PdfParseState.BeginStream;
                        OnStream(_currentObject.Identifier);
                        OnEndObject(crossReference.ObjectReference);
                    }

                    // We have notified the clients, and handled the stream.
                    hasNotified = true;
                    return true;
                };

                // Start parsing
                _currentObject.Parse(lexer);

                // If the listeners have not yet been notified of this object, do it now.
                if (false == hasNotified)
                {
                    OnObject(_currentObject);
                    OnEndObject(crossReference.ObjectReference);
                }

                // We are now in the free state.
                _state = PdfParseState.Free;
            }
            else
                throw new PdfParserException("The object in cross-reference '{0}' could not be located.", crossReference);
        } // SeekAndParse()

        /// <summary>
        /// Seeks the object indicated by the specified cross-reference, and returns a PDF lexer
        /// capable of reading its contents.
        /// If the object could not be found then this method returns a Null reference.
        /// </summary>
        /// <param name="crossReference">The cross-reference</param>
        /// <returns>A suitable PDF lexer for the object.</returns>
        private PdfLexer SeekObject(CrossReference crossReference)
        {
            System.Diagnostics.Debug.Assert(null != crossReference);

            PdfLexer result = null;

            switch (crossReference.Type)
            {
                case CrossReferenceType.FileOffset:
                    // Locate the object, and parse it.
                    _lexer.Seek(crossReference.Location, SeekOrigin.Begin);
                    result = _lexer;
                    break;

                case CrossReferenceType.ObjectStream:
                    // ...
                    break;
            }

            return result;
        } // SeekObject()

        /// <summary>
        /// Seeks the specified object, and returns a PDF lexer capable of reading
        /// its contents.
        /// This method will look up the object in the cross-reference tables, and then
        /// seek it using the information in its cross-reference entry.
        /// This method throws an exception if the object does not appear in the
        /// cross-reference tables.
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        private PdfLexer SeekObject(PdfObjectReference obj)
        {
            if (null == obj) throw new ArgumentNullException("obj");
            if (obj.IsEmpty()) throw new ArgumentException("PDF Object reference cannot be empty", "obj");

            CrossReference crossReference = _crossReferences.Find(match => match.Equals(obj));

            return SeekObject(crossReference);
        } // SeekObject()
        #endregion

        #region Reading streams
        /// <summary>
        /// Reads a chunk of binary data from the lexer.
        /// </summary>
        /// <param name="buffer">The buffer to copy the data into.</param>
        /// <param name="startIndex">The start index in the buffer to begin copying data into.</param>
        /// <param name="length">The number of bytes to read.</param>
        /// <returns>The number of bytes that were read.</returns>
        private int ReadBinaryStreamChunk(byte[] buffer, int startIndex, int length)
        {
            int result = 0;

            // If we have just started to read from the stream, we find out how many bytes
            // there are to read, and ignore the whitespace that follows all stream declarations.
            if (PdfParseState.BeginStream == _state)
            {
                _lexer.Read(); // read whitespace
                _state = PdfParseState.InStream;
            }

            int bufferSpace = Math.Min(length, buffer.Length - startIndex);
            int bytesRead = 0;
            do
            {
                bytesRead = _lexer.FetchBlock(Math.Min(_bytesLeft, bufferSpace));
                Array.Copy(_lexer.Buffer, _lexer.TokenStart, buffer, startIndex, bytesRead);

                // ... next block
                _bytesLeft -= bytesRead;
                bufferSpace -= bytesRead;
                startIndex += bytesRead;
                result += bytesRead;

            } while (bytesRead > 0 && _bytesLeft > 0 && bufferSpace > 0);

            return result;
        } // ReadBinaryStreamChunk()

        /// <summary>
        /// Reads a chunk of PDF token data from the lexer.
        /// </summary>
        /// <param name="buffer">The buffer to copy the data into.</param>
        /// <param name="startIndex">The start index in the buffer to begin copying data into.</param>
        /// <param name="length">The number of bytes to read.</param>
        /// <returns>The number of bytes that were read.</returns>
        private int ReadPdfTokenStreamChunk(byte[] buffer, int startIndex, int length)
        {
            int bytesRead = 0;

            // Setup the lexer to deal with stream content.
            _lexer.Mode = PdfLexerMode.Binary;

            if (PdfParseState.EndStream != _state)
            {
                // If this is the start of the stream then we need to read past the 'stream' and newLine tokens.
                bool moreTokens = true;
                if(PdfParseState.BeginStream == _state)
                {
                    _lexer.Read();
                    moreTokens = _lexer.Read();
                    _state = PdfParseState.InStream;
                }

                // Read PDF tokens until we find the end of the stream or the buffer cannot hold
                // the current token.
                int bufferSpace = Math.Min(length, buffer.Length - startIndex);
                int tokenLength = _lexer.TokenLength;
                while (true == moreTokens && tokenLength < bufferSpace)
                {
                    // Check for 'endstream'
                    if (PdfTokenType.Token == _lexer.TokenType)
                    {
                        int index, finger = _endStream.Length - 1;
                        for (index = _lexer.TokenLength - 1; index >= Math.Max(0, _lexer.TokenLength - _endStream.Length); index--)
                            if (_lexer.Buffer[_lexer.TokenStart + index] != _endStream[finger--]) break;

                        if (finger < 0)
                        {
                            moreTokens = false;
                            break;
                        }
                    }

                    // Copy the token into the buffer.
                    Array.Copy(_lexer.Buffer, _lexer.TokenStart, buffer, startIndex + bytesRead, tokenLength);
                    bufferSpace -= tokenLength;
                    bytesRead += tokenLength;

                    // Read the next token.
                    moreTokens = _lexer.Read();
                    tokenLength = _lexer.TokenLength;
                }

                if (false == moreTokens)
                    _state = PdfParseState.EndStream;
            }

            return bytesRead;
        } // ReadBinaryStreamChunk()
        #endregion

        #region Cross-reference tables and streams
        /// <summary>
        /// Decodes a cross-reference stream contained within the specified PDF object.
        /// </summary>
        /// <param name="xrefObject">The object containing the cross-reference stream.</param>
        /// <returns>The cross-reference table</returns>
        private Stream DecodeCrossReferenceStream(PdfObject xrefObject)
        {
            // Allocate a buffer large enough to hold the stream contents.
            int streamLength = xrefObject.Dictionary.GetInt32Value("/Length");
            byte[] buffer = new byte[streamLength];
            
            // Read the stream contents.
            _lexer.Read(); // whitespace
            int bytesLeft = streamLength;
            int totalBytes = 0;
            int bytesRead = 0;
            do
            {
                bytesRead = _lexer.FetchBlock(bytesLeft);
                Array.Copy(_lexer.Buffer, _lexer.TokenStart, buffer, totalBytes, bytesRead);
                totalBytes+=bytesRead;
                bytesLeft -= bytesRead;
            } while (bytesRead > 0 && totalBytes < streamLength);

            //  Return the deflated stream.
            return new DeflateStream(
                new MemoryStream(buffer, 2, buffer.Length-2),
                CompressionMode.Decompress);
        }

        /// <summary>
        /// Finds the start location in the PDF stream of the first xref table.
        /// </summary>
        /// <returns>The location</returns>
        private long FindStartXRef()
        {
            long startXRef = 0L;

            // We start the lexer at the document tail and wait for the appropriate token to be read.
            _lexer.Seek(-128, SeekOrigin.End);
            _lexer.Mode = PdfLexerMode.Binary;

            bool foundStartToken = false;
            while (0 == startXRef && _lexer.Read())
            {
                if (false == foundStartToken)
                {
                    if ("startxref" == _lexer.Value)
                    {
                        foundStartToken = true;
                        _lexer.Mode = PdfLexerMode.Pdf;
                    }
                }
                else
                {
                    if (PdfTokenType.Token == _lexer.TokenType || PdfTokenType.Number == _lexer.TokenType)
                        startXRef = ConversionUtilities.ReadLong(_lexer.Value);
                }
            }

            return startXRef;
        } // FindStartXRef()

        /// <summary>
        /// Indicates if the specified object is listed in the document's cross-reference tables.
        /// </summary>
        /// <param name="obj">The object</param>
        /// <returns>True if the object is listed; False if it is not.</returns>
        private bool IsListed(PdfObjectReference obj)
        {
            return _crossReferenceLookup.ContainsKey(obj);
        }

        /// <summary>
        /// Reads the cross-reference stream object at the lexer's current position.
        /// This method returns the next set of cross-reference tables, as a byte offset relative to the
        /// start of the file. If there are no more cross-reference tables, this method returns 0.
        /// This method also outputs the object reference of the cross-reference stream.
        /// </summary>
        /// <param name="tableLocations">The list of cross-reference tables to add to.</param>
        /// <returns>The cross-reference stream's object reference.</returns>
        private PdfObjectReference ReadCrossReferenceStream(Stack<long> tableLocations)
        {
            // Read the cross-reference stream object.
            // We parse the stream into a buffer and use that to read the cross-reference.
            PdfObject xrefObject = new PdfObject();
            xrefObject.Stream += delegate() {

                bool isHandled = false;

                if (false == xrefObject.Identifier.IsEmpty())
                {
                    // We find a suitable decoder for the stream.
                    string method = xrefObject.Dictionary["/Filter"];
                    DecoderStream table = DecoderStream.GetDecoder(method);
                    if (null != table)
                    {
                        // Now we can set up the decoder and read the xref table from it.
                        int length = xrefObject.Dictionary.GetInt32Value("/Length");
                        _lexer.Read(); // whitespace
                        table.Initialise(
                            _lexer.OpenStream(length),
                            xrefObject.Dictionary.GetDictionary("/DecodeParms"));

                        ReadCrossReferenceStreamTable(table, xrefObject);

                        // Tell the object that we've handled the stream.
                        isHandled = true;
                    }
                    else
                        throw new PdfParserException("No decoder was found for filter '{0}'", method);
                }

                return isHandled;
            };

            xrefObject.Parse(_lexer);

            // The next table is indicated by the /Prev field in the object's dictionary.
            long nextTable = xrefObject.Dictionary.GetInt32Value("/Prev");
            if (nextTable > 0)
                tableLocations.Push(nextTable);

            PdfObjectReference documentRoot =  xrefObject.Dictionary.GetObjectReference("/Root");
            if (null != documentRoot && false==documentRoot.IsEmpty())
                _documentRoot = documentRoot;

            // Output the object reference of this cross-reference stream.
            return xrefObject.Identifier;

        } // ReadCrossReferenceStream()

        /// <summary>
        /// Parses the cross-reference stream's format parameters.
        /// </summary>
        /// <param name="xrefObject">The object that contains the cross-reference stream.</param>
        /// <returns>The format</returns>
        private int[] ReadCrossReferenceStreamFormat(PdfObject xrefObject)
        {
            int[] format = new int[3];

            PdfList widths = xrefObject.Dictionary.GetList("/W");
            if (null != widths)
                for (int index = 0; index < Math.Min(3, widths.Count); index++)
                    format[index] = widths.GetInt32Value(index);
            
            return format;
        }

        /// <summary>
        /// Reads the index of a cross-reference table.
        /// </summary>
        /// <param name="xrefObject">The object that contains the cross-reference stream.</param>
        /// <returns>The index</returns>
        private int[] ReadCrossReferenceStreamIndex(PdfObject xrefObject)
        {
            List<int> index = new List<int>();

            // The index is a set of pairs of numbers. It defaults to {0,(size)} where (size) is the
            // value of the /Size entry in the object.
            PdfList indexObjects = xrefObject.Dictionary.GetList("/Index");
            int size = xrefObject.Dictionary.GetInt32Value("/Size");

            if (null != indexObjects && indexObjects.Count > 1)
            {
                // We convert each pair to numbers, and add these.
                int finger = 0;
                while(finger < indexObjects.Count)
                {
                    int firstObject = indexObjects.GetInt32Value(finger++, -1);
                    if(finger<indexObjects.Count)
                    {
                        int numberOfEntries = indexObjects.GetInt32Value(finger++,0);

                        if (firstObject>=0 && numberOfEntries>0)
                        {
                            index.Add(firstObject);
                            index.Add(numberOfEntries);
                        }
                    }
                }
            }
            else
            {
                // Default index is {0, (size)}
                index.Add(0); index.Add(size);
            }

            return index.ToArray();
        } // ReadCrossReferenceStreamIndex()

        /// <summary>
        /// Parses the contents of a cross-reference stream's object table.
        /// </summary>
        /// <param name="table">The table's contents stream</param>
        /// <param name="xrefObject">The object that contains the cross-reference table</param>
        private void ReadCrossReferenceStreamTable(
            Stream table, 
            PdfObject xrefObject)
        {
            // Read the field widths and sub-table indices.
            int[] widths = ReadCrossReferenceStreamFormat(xrefObject);
            int[] index = ReadCrossReferenceStreamIndex(xrefObject);
            int columns = 1; foreach(int width in widths) columns+=width;

            // Parse objects while there are sub-tables to parse.
            int indexFinger = 0;
            PdfObjectReference objectInTable = PdfObjectReference.Empty;
            CrossReference crossReference = null;
            while (indexFinger < index.Length)
            {
                int firstObject = index[indexFinger++];
                int objectCount = index[indexFinger++];

                // Read all the objects in this table, and create cross-references for them.
                for (int objectEnum = 0; objectEnum < objectCount; objectEnum++)
                {
                    long entryType = ReadStreamValue(table, widths[0]);
                    switch (entryType)
                    {
                        case 0:
                        default:
                            // This is a type 0 entry - it lists unused objects. We ignore it.
                            ReadStreamValue(table, widths[1]);
                            ReadStreamValue(table, widths[2]);
                            crossReference = null;
                            break;

                        case 1:
                            // This is a type 1 entry - a direct, uncompressed object. We create a cross-reference
                            // for the object so we now where to find it after we're done with all the tables.
                            long location = ReadStreamValue(table, widths[1]);
                            int generation = (int)ReadStreamValue(table, widths[2]);

                            objectInTable = new PdfObjectReference(firstObject + objectEnum, generation);
                            crossReference = new CrossReference(
                                objectInTable,
                                location);

                            break;

                        case 2:
                            // This is a type 2 entry - a compressed object stored inside the stream of
                            // another object.
                            // We create a cross-reference for this object, too, but will specify the
                            // parent object and index instead of a file location.
                            // These values are used to provide random-access to the object.
                            PdfObjectReference parentObject = new PdfObjectReference(
                                (int)ReadStreamValue(table, widths[1]));
                            int parentIndex = (int)ReadStreamValue(table, widths[2]);
                            
                            objectInTable = new PdfObjectReference(firstObject + objectEnum, 0);
                            crossReference = new CrossReference(
                                objectInTable,
                                parentObject,
                                parentIndex);

                            // We add te parent object to the list of object streams.
                            if (false==_objectStreams.Contains(parentObject))
                                _objectStreams.Add(parentObject);
                            break;
                    }

                    // Add the cross-reference to the list.
                    if (null!=crossReference && false == IsListed(objectInTable))
                    {
                        _crossReferences.Add(crossReference);
                        _crossReferenceLookup[objectInTable] = crossReference;
                    }

                } // for each object
            } // while there are sub-tables

        } // ReadCrossReferenceStreamTable()

        /// <summary>
        /// Reads the cross-reference trailer, and returns the location of the next table in the list.
        /// </summary>
        /// <returns>The location of the next table in the list, or 0 if there is no next table.</returns>
        /// <param name="tableLocations">The list of table locations to add to.</param>
        private void ReadCrossReferenceTrailer(Stack<long> tableLocations)
        {
            long previousLiteral = 0L;
            long xrefStream = 0L;

            bool finished = false;
            while (false==finished && _lexer.Read())
            {
                switch (_lexer.TokenType)
                {
                    case PdfTokenType.DictionaryEnd:
                        finished = true;
                        break;

                    case PdfTokenType.Name:
                        string tokenName = _lexer.Value;
                        switch (tokenName)
                        {
                            case "/Prev":
                                previousLiteral = ConversionUtilities.ReadLong(_lexer.ReadNextToken());
                                break;

                            case "/XRefStm":
                                xrefStream = ConversionUtilities.ReadLong(_lexer.ReadNextToken());
                                break;

                            case "/Root":
                                int identifier = ConversionUtilities.ReadInt32(_lexer.ReadNextToken());
                                int secondary = ConversionUtilities.ReadInt32(_lexer.ReadNextToken());
                                _lexer.ReadPastWhitespace();
                                if (PdfTokenType.R == _lexer.TokenType)
                                    _documentRoot = new PdfObjectReference(identifier, secondary);
                                break;
                        }
                        break;
                }
            }

            // The /Prev value indicates the position of the next table in the chain.
            // In 'hybrid' PDF 1.5 documents, the /XrefStm value may be used as well.
            // The table pointed to by /XrefStm must be processed before the one
            // referenced by /Prev.
            if (previousLiteral > 0) tableLocations.Push(previousLiteral);
            if (xrefStream > 0) tableLocations.Push(xrefStream);

        } // ReadCrossReferenceTrailer

        /// <summary>
        /// Reads all the cross-reference tables, and returns the crossReferences within.
        /// </summary>
        /// <param name="startXRef">The start of the first cross-reference table.</param>
        /// <returns>The crossReferences</returns>
        private void ReadCrossReferenceTables(long startXRef)
        {
            List<PdfObjectReference> crossReferenceStreams = new List<PdfObjectReference>();
            
            // We start at the first table, and read tables until there are none left.
            Stack<long> tableLocations = new Stack<long>();
            tableLocations.Push(startXRef);
            while (tableLocations.Count > 0)
            {
                // Fetch the next table from the stack.
                long nextTable = tableLocations.Pop();

                // Find the table
                _lexer.Seek(nextTable, SeekOrigin.Begin);

                // The cross-reference table could either be a literal xref table (as in PDF 1.0-1.4) or
                // a cross-reference stream.
                if ("xref" == _lexer.ReadNextToken())
                    ReadLiteralCrossReferenceTables(tableLocations);
                else
                {
                    _lexer.Seek(nextTable, SeekOrigin.Begin);
                    PdfObjectReference streamReference = ReadCrossReferenceStream(tableLocations);

                    // Mark the cross-reference stream object.
                    if (null!=streamReference && false == streamReference.IsEmpty())
                        crossReferenceStreams.Add(streamReference);
                }
            }

            // After reading all the tables, we remove from the list of cross-references the objects that
            // represent the cross-reference streams. We won't include these in our document.
            _crossReferences.RemoveAll(crossReference => crossReferenceStreams.Contains(crossReference.ObjectReference));

        } // ReadCrossReferenceTables()

        /// <summary>
        /// Reads literal cross-reference tables from the current position in the PDF lexer.
        /// This method returns the address of the next cross-reference table set, as a byte offset
        /// from the start of the file. If there are no more cross-reference tables, the method returns 0.
        /// </summary>
        /// <param name="tableLocations">The list of table locations to add to.</param>
        private void ReadLiteralCrossReferenceTables(Stack<long> tableLocations)
        {
            // Find out which objects the table contains.
            int startIndex = ConversionUtilities.ReadInt32(_lexer.ReadNextToken());
            int length = ConversionUtilities.ReadInt32(_lexer.ReadNextToken());
                
            while (startIndex>=0 && length>0)
            {
                // Read the objects.
                for (int objectEnum = 0; objectEnum < length; objectEnum++)
                {
                    long location = ConversionUtilities.ReadLong(_lexer.ReadNextToken());
                    int generation = ConversionUtilities.ReadInt32(_lexer.ReadNextToken());
                    string status = _lexer.ReadNextToken();
                    
                    PdfObjectReference obj = new PdfObjectReference(startIndex + objectEnum, generation);
                    CrossReference crossReference = new CrossReference(obj, location);

                    // Add the cross-reference to the list.
                    if("n"==status && false == IsListed(obj))
                    {
                        _crossReferences.Add(crossReference);
                        _crossReferenceLookup[obj] = crossReference;
                    }
                }

                // The cross-reference list is either followed by a trailer or by another table.
                string nextToken = _lexer.ReadNextToken();
                if ("trailer" == nextToken)
                { 
                    // We find out if there is another table.
                    ReadCrossReferenceTrailer(tableLocations);
                    break;
                }
                else
                {
                    startIndex = ConversionUtilities.ReadInt32(nextToken);
                    length = ConversionUtilities.ReadInt32(_lexer.ReadNextToken());
                }

            } // as long as there are objects to read

        } // ReadLiteralCrossReferenceTables()

        /// <summary>
        /// Reads a value off a stream. The specified number of bytes will be used to read the
        /// value.
        /// </summary>
        /// <param name="stream">The stream</param>
        /// <param name="bytes">The number of bytes to read.</param>
        /// <returns>The value.</returns>
        private long ReadStreamValue(Stream stream, int bytes)
        {
            long value = 0L;

            for (int part = 0; part < bytes; part++)
            {
                int partValue = stream.ReadByte();
                if (partValue >= 0)
                {
                    value = value << 8;
                    value = value + partValue;
                }
                else
                {
                    value = -1L; break;
                }
            }

            return value;
        }

        /// <summary>
        /// Sorts the cross-references on their location within the stream.
        /// </summary>
        private void SortCrossReferences()
        {
            _crossReferences.Sort( (x, y) =>
            {
                int result = 0;

                if (CrossReferenceType.ObjectStream == x.Type)
                    result = CrossReferenceType.ObjectStream==y.Type ? 0 : 1;
                
                else if (CrossReferenceType.ObjectStream == y.Type)
                    result = -1;

                if (0 == result)
                {
                    if (x.Location < y.Location) result = -1;
                    if (x.Location > y.Location) result = 1;
                }

                return result;
            });
        }
        #endregion



        // Public constructor
        // ==================
        #region Public constructor
        /// <summary>
        /// Constructs a new PdfParser instance.
        /// </summary>
        /// <param name="fin">The input stream</param>
        public PdfParser(Stream fin)
        {
            if (null == fin) throw new ArgumentNullException("fin");

            _crossReferenceLookup = new Dictionary<PdfObjectReference, CrossReference>();
            _crossReferences = new List<CrossReference>();
            _in = fin;
            _lexer = new PdfLexer(fin);
            _objectStreams = new List<PdfObjectReference>();
        }
        #endregion



        // Private types
        // =============
        #region PdfParserState
        /// <summary>
        /// The PdfParseState enumeration lists the possible states that the PdfParser can be in.
        /// </summary>
        private enum PdfParseState
        {
            /// <summary>
            /// In the Free state, the parser has not begun parsing an object. It may be
            /// in between parsing objects.
            /// </summary>
            Free,

            /// <summary>
            /// In the Object state, the parser has begun parsing an object. It has not yet
            /// encountered a stream.
            /// </summary>
            Object,

            /// <summary>
            /// In the BeginStream state, the parser has encountered a stream within an object.
            /// In this state, it is possible to read stream data.
            /// </summary>
            BeginStream,

            /// <summary>
            /// In the InStream state, the parser has read stream data but has not finished.
            /// In this state, it is possible to read stream data.
            /// </summary>
            InStream,

            /// <summary>
            /// In the EndStream state, the parser has read all the stream data.
            /// In this state, reading stream data is allowed but results in no data being
            /// read.
            /// </summary>
            EndStream
        }
        #endregion

        #region ParserStreamType
        /// <summary>
        /// The ParserStreamType enumeration lists the possible types of stream that occur in PDF streams.
        /// </summary>
        private enum ParserStreamType
        {
            /// <summary>
            /// A Binary stream contains data that is copied directly as-is, without its contents being
            /// parsed. A Binary stream has a Filter value set, and must have a Length property.
            /// </summary>
            Binary,

            /// <summary>
            /// The PdfToken stream is contains PDF tokens and does not require a Length property or Filter
            /// value. The tokens are output as they are found, until the 'endstream' token is encountered.
            /// </summary>
            PdfToken
        }
        #endregion

    } // PdfParser()
}
